|
In computational geometry, the Bentley–Ottmann algorithm is a sweep line algorithm for listing all crossings in a set of line segments. It extends the Shamos–Hoey algorithm, a similar previous algorithm for testing whether or not a set of line segments has any crossings. For an input consisting of ''n'' line segments with ''k'' crossings, the Bentley–Ottmann algorithm takes time O((''n'' + ''k'') log ''n''). In cases where ''k'' = o(''n''2 / log ''n''), this is an improvement on a naïve algorithm that tests every pair of segments, which takes O(''n''2). The algorithm was initially developed by ; it is described in more detail in the textbooks , , and . Although asymptotically faster algorithms are now known, the Bentley–Ottman algorithm remains a practical choice due to its simplicity and low memory requirements. ==Overall strategy== The main idea of the Bentley–Ottmann algorithm is to use a sweep line approach, in which a vertical line ''L'' moves from left to right across the plane, intersecting the input line segments in sequence as it moves.〔In the description of the algorithm in , the sweep line is horizontal and moves vertically; this change entails swapping the use of ''x''- and ''y''-coordinates consistently throughout the algorithm, but is not otherwise of great significance for the description or analysis of the algorithm.〕 The algorithm is described most easily in its general position, meaning: #No two line segment endpoints or crossings have the same ''x''-coordinate #No line segment endpoint lies upon another line segment #No three line segments intersect at a single point. In such a case, ''L'' will always intersect the input line segments in a set of points whose vertical ordering changes only at a finite set of discrete ''events''. Thus, the continuous motion of ''L'' can be broken down into a finite sequence of steps, and simulated by an algorithm that runs in a finite amount of time. There are two types of events that may happen during the course of this simulation. When ''L'' sweeps across an endpoint of a line segment ''s'', the intersection of ''L'' with ''s'' is added to or removed from the vertically ordered set of intersection points. These events are easy to predict, as the endpoints are known already from the input to the algorithm. The remaining events occur when ''L'' sweeps across a crossing between two line segments ''s'' and ''t''. These events may also be predicted from the fact that, just prior to the event, the points of intersection of ''L'' with ''s'' and ''t'' are adjacent in the vertical ordering of the intersection points. The Bentley–Ottman algorithm itself maintains data structures representing the current vertical ordering of the intersection points of the sweep line with the input line segments, and a collection of potential future events formed by adjacent pairs of intersection points. It processes each event in turn, updating its data structures to represent the new set of intersection points. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Bentley–Ottmann algorithm」の詳細全文を読む スポンサード リンク
|